The Internet is fast becoming a medium that can provide voice, video, and data services to a large number of users, such as residential users. In order to provide Internet-based voice, video, and data services to a large number of users, the networking equipment at the edge of the network must be able to provide a high level of Quality of Services (QoS) control. QoS control, referred to generally as “traffic management,” involves controlling the rate at which bandwidth is consumed by users as well as ensuring that the quality of time-critical data (e.g., voice and video data) is maintained. The process of controlling the rate at which bandwidth is consumed is generally referred to as “rate shaping” and the process of controlling the quality of time-critical data is generally referred to as “scheduling.”
Traffic management within a network device such as a switch and/or router requires packets to be buffered so that the rate of outgoing traffic can be controlled to meet bandwidth limitations and so that the order of outgoing traffic can be controlled and rearranged as needed to meet the QoS demands. Buffered traffic is typically managed using queues, where each queue is a linked list of information that relates to the packets that are buffered and waiting to be forwarded from the network device.
Conventional traffic management operations involve controlling a few strict priority traffic flows destined to an output port. All of the traffic destined to the same output port is classified into a few different priorities with a separate queue associated with each priority. The number of queues needed to support conventional traffic management within a network device is equal to the number of output ports times the number of different priorities. For example, if a network device has ten output ports and supports four different priorities, then the network device only needs to maintain and manage forty different queues.
In emerging uses, where network devices support Internet-based voice, video, and data services to a large number of residential users, there is a need to maintain a large number of queues. For example, in a network of four-thousand users with each user subscribing to four different applications (2 videos, 1 voice, and 1 data), the network device needs to be able to manage sixteen-thousand different queues. For a relatively small number of queues (e.g., less than 100), traffic management can easily be implemented in software with a high speed CPU. However, as the number of queues increases, it becomes more difficult to implement traffic management in software at a high enough rate to support the expected traffic throughput. In the case of four-thousand different users, if each user subscribes to 10 megabits per second (Mbps) of service, the total throughput required of a network device is 40 gigabits per second (Gbps). Implementing software-based traffic management at 40 Gbps is a difficult task. In view of this, what is needed is a technique for traffic management that supports thousands of different queues and that can be efficiently implemented in hardware in a network processor IC at rates in the range of, for example, 40 Gbps.